package 代码随想录_回溯.力扣_回溯.搜索矩阵;

/**
 * @author zx
 * @create 2022-06-27 18:08
 */
public class 机器人的运动范围_13 {
    /**
     * day_38:红与黑(搜索矩阵问题：类似于剑指offer-13)
     */
    public int movingCount(int m, int n, int k) {
        boolean[][] arr = new boolean[m][n];
        return dfs(arr,0, 0,k);//注意这里,和之前的不一样：(i,j) -> (0,0)
    }
    private int dfs(boolean[][] arr, int i, int j, int k) {
        if(i < 0 || i >= arr.length || j < 0 || j >= arr[0].length) {
            return 0;
        }
        if(arr[i][j] || bitSum(i) + bitSum(j) > k){
            return 0;
        }
        arr[i][j] = true;
        return 1 + dfs(arr,i - 1, j, k) + dfs(arr, i + 1,j, k) + dfs(arr,i,j - 1,k) + dfs(arr,i,j + 1,k);
    }
    //数位之和计算
    private int bitSum(int n) {
        int sum = 0;
        while(n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }
}
